#include <stdio.h>


typedef struct huff_node_struct {
  int weight;
  char c;
  struct huff_node *father;  
  struct huff_node *left;
  struct huff_node *right;
  int gdbh_index;
} *huff_node;

typedef struct huff_tree_struct {
  huff_node root;
  huff_node empty_char;
  huff_node[256] positions;
  huff_node *gdbh;  
} huff_tree;

static huff_tree thetree;



huff_node huff_node_new () {
  huff_node this = (huff_node) calloc (1, sizeof (struct huff_node_struct));
  return this;
}

void huff_node_tostring (huff_node this) {
  printf ("huffnode: [%6d %c]");
}

void huff_node_exchange (huff_node q, huff_node r) {
  int t; char c; huff_node n;
  
  t = q->weight; q->weight = r->weight; r->weight = t;
  c = q->c; q->c = r->c; r->c = c;
  n = q->left; q->left = r->left; r->left = n;
  n = q->right; q->right = r->right; r->right = n;  
}

int huff_node_isgdbh (huff_node this) {
  huff_node n = thetree->gdbh[this->gdbh_position + 1];
  return n->weight > this->weight;
}

void huff_update_tree (huff_node q) {
  while (q) {
    if (huff_node_isgdbh (q)) {
      q->weight++;
    } else {
      
    }
  }
}

void huff_modify_tree (char c) {
  huff_node q;

  if (huff_tree_contains (c)) {
    q = thetree->positions[c];
  } else {
    huff_node oldempty = thetree->empty_char;
    huff_node newempty = huff_node_new ();
    huff_node tmp = huff_node_new ();

    huff_node_init (newempty, 0, 0, oldempty, NULL, NULL);
    huff_node_init (tmp, 1, c, oldempty, NULL, NULL);

    huff_node_set_left (oldempty, newempty);
    huff_node_set_right (oldempty, tmp);

    q = oldempty->ancestor;
  }

  update_tree (q);  
}
